/**
 * //Given a m x n grid filled with non-negative numbers, find a path from top
 * //left to bottom right, which minimizes the sum of all numbers along its path.
 * //
 * // Note: You can only move either down or right at any point in time.
 * //
 * //
 * // Example 1:
 * //
 * //
 * //Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
 * //Output: 7
 * //Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
 * //
 * //
 * // Example 2:
 * //
 * //
 * //Input: grid = [[1,2,3],[4,5,6]]
 * //Output: 12
 * //
 * //
 * //
 * // Constraints:
 * //
 * //
 * // m == grid.length
 * // n == grid[i].length
 * // 1 <= m, n <= 200
 * // 0 <= grid[i][j] <= 100
 * //
 * //
 * // Related Topics 数组 动态规划 矩阵 👍 1314 👎 0
 */

package com.xixi.basicAlgroithms.dynamicPrograming;

public class ID00064MinimumPathSum {
    public static void main(String[] args) {

        Solution solution = new ID00064MinimumPathSum().new Solution();
        System.out.println(solution.minPathSum(new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}));
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        int minSum = Integer.MAX_VALUE;

        public int minPathSum(int[][] grid) {

            //每个格子的最小路径和，只能从上面或者左面较小的那个格子的路径和得来
            int m = grid.length;
            int n = grid[0].length;
            //用一个status来存储最小路径和
            int[][] status = new int[m][n];
            //初始化第一格
            status[0][0] = grid[0][0];
            //上边一行，和左边一列的最小路径和是固定的
            //初始化第一列和第一行
            for (int i = 1; i < m; ++i) {
                status[i][0] = status[i - 1][0] + grid[i][0];
            }
            for (int j = 1; j < n; ++j) {
                status[0][j] = status[0][j - 1] + grid[0][j];
            }

            //动态规划
            for (int i = 1; i < m; ++i) {
                for (int j = 1; j < n; ++j) {
                    status[i][j] = Math.min(status[i - 1][j], status[i][j - 1]) + grid[i][j];
                }


            }


            return status[m - 1][n - 1];
        }


        public void backTracking(int[][] grid, int m, int n, int x, int y, int maxStep, int nowStep, int nowSum) {

            if (nowStep == maxStep) {
                if (nowSum < minSum) {
                    minSum = nowSum;
                }
                return;
            }
            //只能往右或者往下
            int[][] diff = new int[][]{{0, 1}, {1, 0}};

            for (int[] addDiff : diff) {
                int nowX = x + addDiff[0];
                int nowY = y + addDiff[1];

                if (nowX < m && nowY < n) {
                    int add = grid[nowX][nowY];
                    backTracking(grid, m, n, nowX, nowY, maxStep, nowStep + 1, nowSum + add);
                }

            }


        }

    }
//leetcode submit region end(Prohibit modification and deletion)


}